package com.s6.sort3;

import java.util.Arrays;

public class RadixSort {

	public static void main(String[] args) {
		int[] array = { 21, 54, 32, 10, 32, 10, 78, 100};
		sortInteger(array);
		System.out.println("array = " + Arrays.toString(array));
				
		String[] strArray = { "13874768338",  "13888888888",  "13844444444",  "15113881388"};	
		sortNumberString(strArray);
		System.out.println("strArray = " + Arrays.toString(strArray));
		
		// a-z 97 122
		strArray = new String[] { "hke",  "iba",  "hzg",  "ikf", "hac"};	
		sortLetters(strArray);
		System.out.println("strArray = " + Arrays.toString(strArray));
	}

	private static void sortLetters(String[] strArray) {
		int length = strArray[0].length();
		for (int i = length - 1; i >= 0; i--) {
			countingCharacter(strArray, i);
		}
	}

	private static void countingCharacter(String[] strArray, int index) {
		if (strArray.length <= 1) {
            return;
        }
        
		// 定义计数数组  c 数组，数组长度为区间['0', '9']
		int[] c = new int['z' - 'a' + 1];
		
		String value;
		int i, k;
		// 填充 c 数组
		for (i = 0; i < strArray.length; i++) {
			// 数值到计数数组的匹配关系
			c[value2IndexCharacter(strArray[i], index)]++;
		}
		
		// c 会累加各项目的值
		for (i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}
		
		// 创建临时数组newArr，存储排序之后的结果 
		String[] newArr = new String[strArray.length];
		for (i = strArray.length - 1; i >= 0; i--) {
			// 根据数值
			value = strArray[i];
			// 找到对应的 c 下标对应的位置 k
			k = value2IndexCharacter(value, index);
			// k取出 c[k] 的位置，再自减去得到 arr 位置
			c[k]--;
			// 赋值到 newArr
			newArr[c[k]] = value;
		}
		
		// newArr 取代 arr
		for (i = strArray.length - 1; i >= 0; i--) {
			strArray[i] = newArr[i];
		}
	}

	private static int value2IndexCharacter(String value, int index) {
		return value.charAt(index) - 'a';
	}

	private static void sortNumberString(String[] strArray) {
		int length = strArray[0].length();
		for (int i = length - 1; i >= 0; i--) {
			// [length -1, 0]
			countingSort(strArray, i);
		}
	}

	private static void countingSort(String[] strArray, int index) {
		if (strArray.length <= 1) {
            return;
        }
        
		// 定义计数数组  c 数组，数组长度为区间['0', '9']
		int[] c = new int['9' - '0' + 1];
		
		String value;
		int i, k;
		// 填充 c 数组
		for (i = 0; i < strArray.length; i++) {
			// 数值到计数数组的匹配关系
			c[value2Index(strArray[i], index)]++;
		}
		
		// c 会累加各项目的值
		for (i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}
		
		// 创建临时数组newArr，存储排序之后的结果 
		String[] newArr = new String[strArray.length];
		for (i = strArray.length - 1; i >= 0; i--) {
			// 根据数值
			value = strArray[i];
			// 找到对应的 c 下标对应的位置 k
			k = value2Index(value, index);
			// k取出 c[k] 的位置，再自减去得到 arr 位置
			c[k]--;
			// 赋值到 newArr
			newArr[c[k]] = value;
		}
		
		// newArr 取代 arr
		for (i = strArray.length - 1; i >= 0; i--) {
			strArray[i] = newArr[i];
		}
	}

	private static int value2Index(String string, int index) {		
		return string.charAt(index) - '0';
	}

	/**
	 * 基数排序
	 * 
	 * @param arr
	 */
	public static void sortInteger(int[] arr) {
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		int radix = 10;
		// 从个位开始，对数组arr按"指数"进行排序
		for (int exp = 1; max / exp > 0; exp *= radix) {
			countingSort(arr, exp, radix);
		}
	}
	
    /**
     * 计数排序-对数组按照"某个位数"进行排序
     *
     * @param arr
     * @param exp 指数
     */
    public static void countingSort(int[] arr, int exp, int radix) {
        if (arr.length <= 1) {
            return;
        }
        
		// 定义计数数组  c 数组，数组长度为区间[0, 9]
		int[] c = new int[radix];
		
		int i, j, k;
		// 填充 c 数组
		for (i = 0; i < arr.length; i++) {
			// 元素到计数数组的匹配关系
			c[value2Index(arr[i], exp, radix)]++;
		}
		
		// c 会累加各项目的值
		for (i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}
		
		// 创建临时数组newArr，存储排序之后的结果 
		int[] newArr = new int[arr.length];
		for (i = arr.length - 1; i >= 0; i--) {
			// 根据数值
			j = arr[i];
			// 找到对应的 c 下标对应的位置 k
			k = value2Index(j, exp, radix);
			// k取出 c[k] 的位置，再自减去得到 arr 位置
			c[k]--;
			// 赋值到 newArr
			newArr[c[k]] = j;
		}
		
		// newArr 取代 arr
		for (i = arr.length - 1; i >= 0; i--) {
			arr[i] = newArr[i];
		}
    }
    
    // i 在 c 数组中的位置
    private static int value2Index(int value, int exp, int radix) {
    	return value / exp % radix;
    }

}
